package strategy.demo;//Java program to sort the elements using Heap sort

public class HeapSortStrategy implements SortStrategy {
    @Override
    public void sort(int arr[]) {

        int size = arr.length; //Assigning the length of arr in a variable
// Create heap
        for (int i = size / 2 - 1; i >= 0; i--)
            heapify(arr, size, i);
//Find the maximum element and replace it with the last element in the arr
        for (int i = size - 1; i >= 0; i--) {
            int x = arr[0];//largest element(It is available in the root)
            arr[0] = arr[i];
            arr[i] = x;
// Recursively call heapify until a heap is formed
            heapify(arr, i, 0);
        }
    }

    // Heapify function
    void heapify(int array[], int SizeofHeap, int i) {
        int largestelement = i; // Set largest element as root
        int leftChild = 2 * i + 1; // index of left child = 2*i + 1
        int rightChild = 2 * i + 2; //index of right child  = 2*i + 2
// left child is greater than root
        if (leftChild < SizeofHeap && array[leftChild] > array[largestelement])
            largestelement = leftChild;
//right child is greater than largest
        if (rightChild < SizeofHeap && array[rightChild] > array[largestelement])
            largestelement = rightChild;
// If largestelement is not root
        if (largestelement != i) {
            int temp = array[i];
            array[i] = array[largestelement];
            array[largestelement] = temp;
// Recursive call to  heapify the sub-tree
            heapify(array, SizeofHeap, largestelement);
        }
    }


}